(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "Deterministic graphical games"

LIBKAKY 

RESEARCH REPORTS ~mm 
NAVAL POSTGRADUATE SCH 
MONTEREY, CALIFORNIA 93i 



NPS-55-86-010 



NAVAL POSTGRADUATE SCHOOL 

Monterey, California 




TECHNICAL 



DETERMINISTIC GRAPHICAL GAMES 



ALAN R. WASHBURN 



MAY 1986 



Approved for public release: distribution unlimited 



FedDocs 

D 208.14/2 

NPS-55-86-010 



Prepared for: 
val Postgraduate School 
nterey, CA 93943-5000 



. 



NAVAL POSTGRADUATE SCHOOL 
MONTEREY, CALIFORNIA 



Rear Admiral R. H. Shumaker D. A. Schrady 

Superintendent Provost 



Reproduction of all or part of this report is authorized. 
This report was prepared by: 



L 



XTiHirv m A^s.-n ATION O- 'H-S P^jt 



mP L EVKNOXUBKAHV 



REPORT DOCUMENTATION PAGE ^^LTOgTORADlWlg 8CHC 



MOWEREV CA WW34jff 



J"Rl ORT SECURITY CLASSlflCATION 

UNCLASSIFIED 



lb RESTRICTIVE MARKINGS 



a. SECURITY CLASSIFICATION AUTHORITY 



D DECLASSIFICATION /DOWNGRADING SCHEDULE 



j DISTRIBUTION/ AVAILABILITY OF REPORT 

Approved for public release; distribution 
unl imited. 



PERFORMING ORGANIZATION REPORT NUMBE R("s') 

NPS55-86-010 


5 MONITORING ORGANIZATION REPORT NUMBER(S) 




j NAME OF PERFGRMiNU ORGANIZATION 

Naval Postgraduate School 


bD OFFICE SYMBOL 
(If applicable) 

Code 55 


7d NAME OF MONITORING ORGANIZATION 



c. ADDRESS {City. State, and ZIP Code) 

Monterey, CA 93943-5000 



7b. ADDRESS (dry. State, and ZIP Code) 



j, NAME OF FUNDING /SPONSORING 
ORGANIZATION 



80 OFFICE SYMBOL 
(// applicable) 



9 PROCUREMENT INSTRUMENT IDENTIFICATION NUMBER 



ADDRESS (City. State, and ZIP Code) 



10 SOURCE OF FUNDING NUMBERS 



PROGRAM 
ELEMENT NO 



D ROJECT 
NO 



TASK 
NO. 



WORK UNIT 
ACCESSION NO 



Title (inciuae Security Classification) 



DETERMINISTIC GRAPHICAL GAMES 



! PERSONAL AUTHOR(S) 

Washburn. Alan R. 



a. TYPE OF REPORT 

Technical 



13b. TIME COVERED 
FROM TO 



14. DATE OF REPORT (Year, Month, Day) 
1986 Mav 



15 PAGE COUNT 

1-3 



i SUPPLEMENTARY NOTATION 



COSATI CODES 


18 SUBJECT TERMS (Continue on reverse it necessary and identify by block number) 


FIELD 


GROUP 


SUB-GROUP 


Game, Chess, Graph 

















I ABSTRACT (Continue on reverse it necessary and identify by block numoer) 

This paper gives a simple algorithm for solving a class of graphical games where 
infinite play is possible. 



) DISTRIBUTION/ AVAILABILITY OF ABSTRACT 
_GQuNCLASSlFlED/UNLlMlTED D SAME AS RPT D OTIC USERS 



21 ABSTRACT SECURITY CLASSIFICATION 

UNCLASSIFIED 



a NAME OF RESPONSIBLE INDIVIDUAL 

Man R. Washburn 



M 



22b TELEPHONE (include AreaCoae) 

408-646-2381 



22c OFFICE SYMBOL 

Code 55Ws 



3 FORM 1473, aa mar 



BJ APR coition may be used until e/nausted 
All other editions are obsolete 



SECURITY CLASSIFICATION OF THIS PAGE 



DETERMINISTIC GRAPHICAL GAMES 



Abstract 

This paper gives a simple algorithm for solving a class 
of graphical games where infinite play is possible. 



Introduction 

A Deterministic Graphical (DG) game is a two person zero sum game 
played on a directed graph with n > nodes. Nodes are of two kinds: 
terminal and continuing. Terminal nodes are those with no successors, and 
have a payoff to player 1 associated with them. Continuing nodes have at 
least one successor, and are labelled to indicate which player chooses the 
successor. Play begins at some specified node, and continues until a 
terminal node is reached. If no terminal node is ever reached, the payoff 
is by convention 0. Our main intention in this paper is to describe an 
algorithm for solving DG games in o(n 3 ) steps. 

The reader may not welcome our introduction of a new term for what may 
seem like a familiar class of games. However, DG games are actually a 
slightly new topic. The deterministic Perfect Information games of von 
Neumann and Morgenstern (1944) and also Kuhn (1953) are restricted to be 
trees, which makes them a special case. It is true that DG games for which 
infinite play is impossible (tic-tac-toe is a good example) can always be 
put in the form of a tree by replicating nodes, but that operation can 
greatly increase the number of nodes. Besides, there are interesting DG 
games for which infinite play is possible. Chess is one of these; the 
FIDE rules (Harkness, 1956) permit a draw to be demanded in certain cases 
where no conclusion is in sight, but never force a draw merely on account of 
game length. The Perfect Information games of Berge (1957, 1962) are closer 



to DG games, but differ in that the payoff is influenced by all positions 
(nodes) encountered in play, rather than only the terminal node. Several 
authors have studied games similar to DG games where only two or three 
payoffs are possible (Zermelo (1912), Holladay (1957), Smith (1966)). Smith 
(1966) even comments that games with many possible payoffs are in principle 
solvable by any method that can solve games with only two. Nonetheless, the 
DG class has heretofore been nameless. 

DG games are interesting because they seem to be the largest class of 
"games of perfect information" that simultaneously permits parsimonious 
representation and efficient computation. The possibility of infinite play 
is explicit in DG games, even though the representation of a DG game is 
itself finite. This permits the parsimonious representation of games 
wherein a position can be repeated, without resort to devices such as move 
counters or additional rules that simply prohibit repetition. Introducing a 
large limit on the number of moves typically does not change the value of a 
game, but does have the effect of greatly expanding the number of nodes in 
its graphical representation. Pultr and Morris (1984) show that prohibiting 
repetitions complicates the computational problem in an essential way. The 
most natural thing to do in the presence of potentially infinite play seems 
to be to simply permit it, which is consistent with representation as a DG 
game. DG games are solvable in polynomial time in spite of the possibility 
of infinite play, as will be shown below. 

The fact that the payoff for infinite play in a DG game is assumed to 
be is not really restrictive, since the addition of any constant to all 
the payoffs of a game is strategically neutral. The assignment of payoff 
to infinite play is simply an analytical convenience. 



We now offer the following formal 



Definition : . A DG game is a directed graph with finitely many 
nodes partitioned into three sets: S 1 (S 2 ) is the set of nodes 
where player 1 (player 2) chooses the successor, and T is the set 
of terminal nodes on which some real payoff function F is 
defined. The successor function is r, with rx being empty if and 
only if xeT. 



Recursive Games and Solvability 

DG games are special cases of Recursive Games. Everett (1957) has 
therefore shown that all DG games have values, and, since the game element 
corresponding to each node has a trivial minimax solution, that optimal 
stationary strategies exist. Since the existence of stationary strategies 
is guaranteed, we will omit the word "stationary" in what follows. A 
strategy Oi for player 1 is then simply a choice of a successor node in Tx 
for each xeS^ to be used at every opportunity if x arises more than once. 
Strategies for player 2 are defined similarly. 

Definition : If H is some subset of the nodes of DG, we say that DG is 
solvable over H if there is a pair of strategies (a x ,a 2 ) and a real function 
W defined on the nodes of DG such that if the initial node is xeH, 

a) all successors of x will remain in H and the payoff will be 
at least Wx as long as player 1 employs a lf and 

b) all successors of x will remain in H and the payoff will be 
at most Wx as long as player 2 employs o 2 

DG will be said to be solvable if it is solvable over all nodes. 

We wish to show that DG is solvable. Our method will be to show that 
DG is solvable over T, and that the set of nodes for which DG is solvable 



can always be expanded if it is incomplete. We will frequently take 
advantage of the fact that, if properties a) and b) above hold for an 
"initial" node xeH, they will also hold if node x is chosen any time before 
the game terminates; this follows from the stationarity of the strategies 
being considered. 

Preparatory Lemmas 

L emma 1 

Suppose that DG is solvable over H, that T c H, and that there is some 
node yeH for which rye H. Then the game is solvable over HU ty}. 

Proof 

Let o lf o 2 > and W solve DG over H, and suppose yeS 1 . We will modify 
the strategies and extend W to include y, so that DG is solved over H {y}. 

The extension is 

Wy = max Wz ( 1 ) 

zeTy 

If z is any maximizing node in (1), let a/ be identical to afj except that 
player 1 maps y into z. Since o/ agrees with o x on H, o l * guarantees that 
all successors of nodes in H will remain in H, and therefore the same thing 
is true of nodes in Hij{y}. Furthermore, a x ' guarantees at least Wx for 
xeH {y}; any exception would contradict the fact that o x guarantees Wx for 
xeH. This establishes property a) for a l 1 and Hu(y). To establish 



property b) for o 2 and H u(y}, we have only to note that rye H, which 
guarantees that successors of y remain in Hu(y) (in H, in fact) regardless 
of the strategy employed by player 1, and also note that Wy is defined to be 
a maximum, which means that no payoff larger than Wy is possible from node y 
as long as player 2 employs o 2 . This completes the proof of lemma 1 for the 
case where yeS 1 . Since TcH, the only other possibility is that yeS 2 , in 
which case take 

Wy = min Wz (2) 

zeTy 

and define o 2 ' to be a 2 except that player 2 maps y into z. The rest of the 
proof is similar. 

Lemma 1 assumed the existence of a node yeH for which Tyc H. In the 
next lemma, we assume that such a node does not exist. 

Lemma 2 

Suppose that DG is solvable over H, that TcH, and that H n ry is not 
empty for any yeH. Then there exists some yeH for which the game is 
solvable over Hu(y). 

Proof: Let o x , a 2 , W solve the game over H. Since by assumption each 
player has the option of mapping nodes in H into H, there are strategies Z x 
for player 1 and Z 2 for player 2 with the properties that l l (Z 2 ) agrees 
with Oi (o 2 ) on H and that Z x (Z 2 ) maps nodes in H into H . Furthermore, 
nodes in H are not successors of nodes in H under either o t or o 2 , and 
therefore Z lt £ 2 , W solves the game over H. Let 



Q. = {(x,i) xeHOS , ieHnrx}; j = 1,2 (3) 

J J 



and let w t = max Wi, and w 2 = min Wi. (4) 

(x.DeQj (x,i)eQ 2 

If Qj (Q 2 ) is empty, let w t be any negative number (w 2 be any positive 
number). Intuitively, w 1 is the best payoff in H obtainable by player 1 
from anywhere in H, and similarly for w 2 and player 2. We will prove the 
lemma in three cases. 

Case 1 (w^O) 

Let (y,z) be any maximizing pair in the definition of w x , let Wy = v 1 , 
and let o/ be a l except that o/ maps y into z. The proof that property a) 
holds for o/ and Hufy! is as in lemma 1. On the other hand player 2 can 
guarantee a payoff of at most Wy from y by employing £ 2 , since under that 
strategy the payoff will not exceed w, if some successor node (necessarily a 
choice of player 1) is in H, or (since H contains no terminal nodes) if 
all successor nodes are in H. Since E 2 agrees with a 2 on H, property b) 
holds for Z 2 and Hu{y}. Therefore a/, Z 2 > w solves G over Hu{y}. 

Case 2 (w 2 ^0) 

Let (y,z) be any minimizing pair in the definition of w 2 , let Wy = w 2 , 
and let o 2 ' be a 2 except that o 2 ' maps y into z. Then Z l , o 2 '» W solves G 
over H^ {y}. The proof is similar to that of case 1. 



Case 3 (w^O and w 2 >0) 

In this case we can take Wy = for all y in H. £, , E 2 , W solves DG 
over all nodes. Note that Z 1 guarantees at least from any node yeH 
because 



a) If player 2 employs any strategy for which some successor of y 
is in H, o x and therefore l x guarantees a non-negative payoff. 

b) If player 2 employs any strategy for which no successor of y is 
in H, Z 1 guarantees a payoff of 0. 



Similarly, E 2 guarantees a payoff of at most from any node in H, and this 
completes the proof of Case 3 and Lemma 2. 

DG Theorem 

All DG games are solvable. 

Proof: Let H = T, and Wx = Fx for xeT. Any DG game is evidently solvable 
over H . If H does not include all nodes, either lemma 1 or lemma 2 
applies, and hence the game is solvable over some set H x that strictly 
includes H . In a similar manner we can generate H 2 , H 3 , etc. Since there 
are only finitely many nodes, we must eventually encounter some H that 
includes all nodes, which means that the game is solvable. 

An Example 

Figure 1 shows the solution of a DG game with 18 nodes. Squares 
represent moves for the maximizer, and circles for the minimizer. All arcs 
are oriented toward the right except for the two that are curved, which are 
oriented to the left. The terminal nodes are marked with numbers that 




CD 



CD 
Q 



O 
.— CO 



ZD 
CD 



o 






oo 



indicate the payoff. The five non-terminal nodes from which the value is 
non-zero have letter labels to indicate the order of computation. Lemma 1 
applies to nodes a,b,c, and e, and case 1 of lemma 2 applies to node d. 
Case 3 of lemma 2 applies to the other four nodes, which are the last nodes 
to enter H and the ones from which optimal play is non-terminating. 

Computational Considerations 

A bound on the computational effort required for a DG game with n nodes 

can be obtained by first observing that the essential operation in applying 

either lemma 1 or 2 is that of comparing two values, one of which has a node 

index. Let h be the number of nodes in the solved set H. A straightforward 

implementation of the DG Theorem would involve a loop in which h is 

incremented by one in every cycle until either case 3 of lemma 2 arises or 

else h=n , whichever comes first. In the worst case, one would have to do a 

comparison for every pair (x,y) where xeH and yeH, a total of h(n-h) 

comparisons when the loop index is h. Summing on h , we obtain a bound of 

n n 

1 h(n^h) comparisons, which is approximately f h(n-h)dh=n 3 /6. The amount 

h=0 

of effort involved is therefore no worse than cubic in the number of nodes. 

The n 3 /6 bound would presumably not be sharp for a careful implementation of 

the DG Theorem, since making h(n-h) comparisons may very well permit the 

addition of multiple nodes to H (all nodes x in H for which Tx H can be 

added to H, for example), and other efficiencies are also possible. 

Random Moves 

There is no conceptual difficulty in introducing random moves into 
graphical games. If finite, such games are still Recursive Games and 



therefore have solutions with stationary strategies. However, the inclusion 
of random moves seems to complicate the solution procedure in an essential 
manner; there is apparently no feature to exploit that is not already 
present in Recursive Games. This is the reason for excluding the 
possibility of random moves in DG games. There are thus two classes of 
graphical games for which a simple solution technique is available, DG games 
being one and finite tree games (possibly with random moves) being the 
other. Backgammon is an example of a game that lies in neither class. 

In Practice 

We have argued that DG games permit a parsimonious representation of 
games such as Chess. It is clear that even a parsimonious representation 
and a polynomial time algorithm will not help much in solving games as 
complicated as the archtype, however. Without taking advantage of symmetry, 
even the representation of tic-tac-toe as a DG game would be a formidable 
task. The French Military Game (Gardner (1963.), Lucas (1895)) comes to mind 
as an example of a non-trival parlor game solvable as a practical matter if 
a determined practioner were to make repeated application of lemmas 1 and 2. 
The main difficulty with parlor games is the work involved in translating 
the rules into graphical notation, rather than the ensuing computations. 
For large DG games expressed directly as graphs, the existence of a 
polynomial time solution algorithm would be more significant. 



10 



References 

Berge, C, Topological Games with Perfect Information, Contributions to the 
Theory of Games, vol _3_, Princeton U. Press, Princeton, NJ, 1957, 
pp 165-178. 

Berge, C, The Theory of Graphs, Methuen and Co. Ltd., London, 1962. 

Everett, H., Recursive Games, Contributions to the Theory of Games , vol 3, 
Princeton U. Press, Princeton, NJ, 1957, pp 47-78. 

Gardner, M., Mathematical Games, Scientific American, October 1963, 
pp 1 24-1 26. 

Harkness, K., The Official Blue Book and Encyclopedia of Chess , David McKay, 
New York, 1956. 

Holladay, J. C, Cartesian Products of Termination Games, Contributions to 
the Theory of Games , vol 3, Princeton U. Press, Princeton, NY, 1957, 
pp 189-200. 

Kuhn , H. W., Extensive Games and the Problem of Information, 

Contributions to the Theory of Games , vol 2, Princeton U. Press, 
Princeton, NJ, 1953, PP 193-216. 

Lucas, M. E. , Recreations Mathematiques , vol 3, Gauthier-Villars , 
Paris, 1895, pp 105-1 1 6. 

Pultr, A., and F. L. Morris, Prohibiting Repetitions Makes Playing 

Games Substantially Harder, Int. Journal of Game Theory 1 3 , 1984, 
pp 27-40. 

Smith, C. A. B. , Graphs and Composite Games, Journal of Comb. Theory 1_, 1966 
pp 51-81. 

von Neumann, J., and 0. Morgenstern, Theory of Games and Economic 
Behaviour , Princeton U. Press, Princeton, NJ, 1944. 

Zermelo, E. , Uber Eine Anwendung Der Mengenlehre Auf Die Theorie 

Des Schachspiels. International Congress of Mathematicians, 5th, 
Cambridge University Press, 1912. 



1 1 



DISTRIBUTION LIST 



Professor F. L. Morris 

School of Computer and Information Sciences 

313 Link Hall 

Syracuse University 

Syracuse, NY 1 3210 

Professor Martin Shubik 
Cowles Foundation 
Yale University 
New Haven, CT 06520 

Professor Guillermo Owen (Code 530n) 
Mathematics Department 
Naval Postgraduate School 
Monterey, CA 939^3-5000 

Library (Code 01 42) 
Naval Postgraduate School 
Monterey, CA 939^3-5000 

Dr. Ales Pultr 
Department of Mathematics 
Charles University 
Sokolovska 83, 
Prague 8 
CZECHOSLOVAKIA 

Professor Matthew J. Sobel 
College of Management 
Georgia Instute of Technology 
Atlanta, GA 30332 

Professor Lyn Thomas 
University of Edinburgh 
Department of Business Studies 
William Robertson Bldg. 
50 George Square 
Edinburgh EH895Y 
UNITED KINGDOM 

Professor Jerzy Filar 
Mathematical Science Department 
John Hopkins University 
Baltimore, MD 21 218 



12 



Professor Alan Goldman 1 

Mathematics Sciences Department 
John Hopkins University 
Baltimore, MD 21218 

Professor William F. Lucas 1 

1598 Beloit 
Claremont, CA 9171 1 

Professor David Blackwell 1 

Statistical Laboratory 

University of California - Berkeley 

Berkeley, CA 9^720 

Professor A. J. Jones 1 

Department of Mathematics 
Royal Holloway College 
University of London 
UNITED KINGDOM 

Research Administration (Code 012) 1 

Naval Postgraduate School 
Monterey, CA 939^3-5000 

Professor Alan R. Washburn (Code 55Ws) 10 

Department of Operations Research 
Naval Postgraduate School 
Monterey, CA 939^3-5000 

Center for Naval Analyses 1 

2000 Beauregard Street 
Alexandria, VA 2231 1 

Operations Research Center, Room E40-1 64 1 

Massachusetts Institute of Technology 
Attn: R. C. Larson and J. F. Shapiro 
Cambridge, MA 02139 

Defense Technical Information Center 2 

Cameron Station 
Alexandria, VA 22314 



13 



DUDLEY KNOX LIBRARY 




3 2768 00336440 7